#include <cstring>
#include "dfa_construct.h"
#include "grate_constants.h"

const int LAST_MASK = (15 << 28);
const int LF_MASK = (1<<28) - 1;
int * lf_last; // Failure function + incoming letter

int SIGMA_LEN;
char * sigma; // Permutation of letters for each node of DFA

int back_pack_mode; // 0 - 4 bits per mask, 1 - 8 bits per mask, 2 - 16 bits per mask
short * back;

vertex_queue * vert_queue;

void make_permut(char* p1, char* p2, int alph_size){
  int i;
  for (i=0; i<alph_size; i++){
    if (get_sval(p1, i) != LONG_MASK){
      set_sval(p1, i, get_sval(p2, get_sval(p1, i)));
    }
  }
}

inline char get_sval(char * s, int c){
  return (c & 1) ? ((s[c>>1] & (LONG_MASK << 4)) >> 4) : (s[(c>>1)] & LONG_MASK);
}

inline void set_sval(char * s, int c, char d){
  if (c & 1){
    s[c >> 1] &= LONG_MASK;
    s[c >> 1] |= (d << 4);
  }
  else{
    s[c >> 1] &= (LONG_MASK << 4);
    s[c >> 1] |= d;
  }
}

inline char get_sigma(int v, int c){
  return get_sval(sigma + v*SIGMA_LEN, c);
}

inline void set_sigma(int v, int c, char d){
  set_sval(sigma + v*SIGMA_LEN, c, d);
}

inline void set_last(int v, char c){
  lf_last[v] &= ~LAST_MASK;
  lf_last[v] |= ((int)(c) << 28);
}

inline char get_last(int v){
  char z = (((lf_last[v] & LAST_MASK) >> 28) & LONG_MASK);
  return (z == 15) ? -1 : z;
}

inline void set_lf(int v, int clf){
  lf_last[v] &= ~LF_MASK;
  lf_last[v] |= clf;
}

inline int get_lf(int v){
  return lf_last[v] & LF_MASK;
}

inline void set_back(int v, int c){
  if (back_pack_mode == 0){
    int mod = v&3;
    back[v>>2] |= (1 << (4*mod + c));
  }
  else if (back_pack_mode == 1){
    int mod = v&1;
    back[v>>1] |= (1 << (8*mod + c));
  }
  else{
    back[v] |= (1 << c);
  }
}

inline bool is_back(int v, int c){
  if (back_pack_mode == 0){
    int mod = v&3;
    return (back[v>>2] & (1 << (4*mod + c))) > 0;
  }
  else if (back_pack_mode == 1){
    int mod = v&1;
    return (back[v>>1] & (1 << (8*mod + c))) > 0;
  }
  else{
    return (back[v]  & (1 << c)) > 0;
  }
}

void construct_dfa(dfa * DFA){
  int alph_size = DFA->alph_size;
  int total = DFA->total;

  SIGMA_LEN = (alph_size + 1) / 2;
  sigma = new char [(total + 1) * SIGMA_LEN];
  memset(sigma, 0xFF, sizeof(char) * (total + 1) * SIGMA_LEN);

  int BACK_SIZE;
  if (alph_size <= 4){
    back_pack_mode = 0;
    BACK_SIZE = (total + 4) / 4;
  }
  else if (alph_size <= 8){
    back_pack_mode = 1;
    BACK_SIZE = (total + 2) / 2;
  }
  else{
    back_pack_mode = 2;
    BACK_SIZE = (total + 1);
  }
  back = new short [BACK_SIZE];
  memset(back, 0, sizeof(short) * BACK_SIZE);

  lf_last = new int [total + 1];
  /*int i;
  for (i=1; i<=total; i++){
    lf_last[i] = 0;
  }*/
  memset(lf_last, 0, sizeof(int) * (total + 1));

  vert_queue = new vertex_queue(DFA->words_num);

  int i;
  for (i=1; i<alph_size; i++){
    (*DFA)[1][i] = 2;
  }
  
  vert_queue->push_vertex(2);
  set_last(1, -1);
  set_lf(1, 1);
  set_lf(2, 1);

  //while (vqbeg != vqend){
  while (!vert_queue->is_empty()){
    /*construct_vertex(vert_queue[vqbeg]);
    vqbeg = (vqbeg + 1) & (vqsize - 1);*/
    construct_vertex(DFA, vert_queue->pop_vertex());
  }

  //read_word("aaabababbbabaaababbbaaabbbaabbbabaaab");

  delete[] sigma;
  delete[] back;
  delete[] lf_last;
  delete vert_queue;
}

void construct_vertex(dfa * DFA, int v){
  int alph_size = DFA->alph_size;
  int c;
  char * zsigma = new char [SIGMA_LEN];
  char clast = get_last(v);
  for (c=0; c<=clast+1; c++){
    if (c >= alph_size) break;
    if (!(*DFA)[v][c]){
      char d = get_sigma(v, c);
      if (d == LONG_MASK){
        d = get_last(get_lf(v)) + 1;
      }
      (*DFA)[v][c] = (*DFA)[get_lf(v)][d];
      set_back(v, c);
    }
    else{
      int u = (*DFA)[v][c];
      if (u < 0){
        (*DFA)[v][c] = 0;
        continue;
      }
      //push_vertex(u);
      vert_queue->push_vertex(u);
      set_last(u, (c > clast) ? c : clast);
      memcpy(sigma + u*SIGMA_LEN, sigma + v*SIGMA_LEN, sizeof(char)*SIGMA_LEN);
      char d = get_sigma(v, c);
      if (d == LONG_MASK){
        d = get_last(get_lf(v)) + 1;
        set_sigma(u, c, d);
      }
      set_lf(u, (*DFA)[get_lf(v)][d]);
      int zv = get_lf(v);
      while (is_back(zv, get_sigma(u, c))){
        memcpy(zsigma, sigma + zv*SIGMA_LEN, sizeof(char) * SIGMA_LEN);
        if (get_sval(zsigma, get_sigma(u, c)) == LONG_MASK){
          set_sval(zsigma, get_sigma(u, c), get_last(get_lf(zv)) + 1);
        }
        make_permut(sigma + u*SIGMA_LEN, zsigma, alph_size);
        zv = get_lf(zv);
      }
    }
  }
  for (c=clast+2; c<alph_size; c++){
    (*DFA)[v][c] = (*DFA)[v][clast + 1];
    if (is_back(v, clast+1)){
      set_back(v, c);
    }
  }
  delete[] zsigma;
}

vertex_queue::vertex_queue(int _size){
  vqsize = 1;
  while (vqsize < _size) vqsize <<= 1;
  vqueue = new int[vqsize];
  vqbeg = 0;
  vqend = 0;
}

vertex_queue::~vertex_queue(){
  delete[] vqueue;
}

void vertex_queue::push_vertex(int v){
  vqueue[vqend] = v;
  vqend = (vqend + 1) & (vqsize - 1);
}

const int vertex_queue::pop_vertex(){
  int res = vqueue[vqbeg];
  vqbeg = (vqbeg + 1) & (vqsize - 1);
  return res;
}

const bool vertex_queue::is_empty() const{
  return (vqbeg == vqend);
}

// DEBUGGING PURPOSES!!!
/*void read_word(const char * word){
  int cv = 1, i;
  for (i=0; word[i]; i++){
    int c = get_sigma(cv, word[i] - 'a');
    if (!dfa[cv*ALPH_SIZE + c]){
      c=c;
    }
    else cv = dfa[cv*ALPH_SIZE + c];
  }
}*/